1. Field of the Invention
The present invention relates to an encoding device for error correction, encoding method for error correction and encoding program for error correction, and more specifically to an encoding device for error correction, encoding method for error correction and encoding program for error correction based on redundancy in data representation.
2. Description of Related Art
Today, the art of the Error-Correcting Codes for correcting errors occurring in communication channels are utilized in the field of all digital communications. Here, although the term of “communication” generally means information transmission between distanced points carried out via communication media, such as a cable or radio, it is not limited to such a narrow meaning in this specification. The concept of “communication” also includes, for example, recording information on a recording medium such as a compact disc in this specification. Sending information is carrying information to a distant place, and recording information is carrying information to a distant (later) time so that one can read it out later, therefore these are same in that both carry information.
What is handled by coding theory is digitized information. The data to send may be what was digitized from audio signals, video signals, etc., or digital data, etc., from a computer. The words “information source” are used to include a generation source of this information, a part which digitizes them, and any other related parts. In many cases, digitized information (data to send) is expressed in bit strings by using two kinds of signs (numbers), 0 and 1, which can be understood if you think of Pulse-Code Modulation (PCM) signals for example. For this reason, also in this specification, data to send shall be expressed in bit strings or more generally in digit sequences.
FIG. 3 shows a model of a communication system. In this figure, a bit string (information bit string) of 0 and 1 is generated as data to send from an information source. An encoder (encoding device for error correction) handles this information bit string by dividing into blocks for every m bits. Each block is called “data to send” and this data to send is denoted as i=(i1, . . . , im).
The encoder outputs a codeword w=(x1, . . . , xn) of n bits (n≧m) corresponding to the data to send i. That is, an n-m extra bit(s) (a redundant bit(s)) is added by this encoder. The n is called a code length, m is called a number of information bit, and this operation is called “encoding”. The codeword sent out in a communication channel is called a transmitted word w, and the communication channel will output a received word v of n bits when the transmitted word w is inputted. Although the transmitted word=the received word if there is no influence of noise of transmission and/or a recording medium, etc., the transmitted word is usually subject to probabilistic changes because of noise. This is called an error and this situation is often expressed with v=w+e, which means an error e is added to the transmitted word in the communication channel. Here, when the j-th bit wj is changed into wj+ej, the e expresses a bit string e=(e1, . . . , en), which is also called an error pattern. A decoder estimates which codeword was transmitted based on the received word v and outputs an estimate of the transmitted word w or estimate of the data i to send.
Note that although the codewords are sent out to an actual transmission path or recording medium as a signal wave form, which may, for example, be a series of pulses, where the pulse-null and pulse-exist represent the 0s and the 1s of the codeword w, respectively, concrete waveforms are not described for convenience of description in this specification.
Now, an encoding of the code length n and the number of information bits m is called an [n, m] encoding, and the resulting set of 2m codewords is called an [n, m] code (See, for example, Japanese Laid-Open (Kokai) Patent Publication No. 2005-110251 and Japanese Patent No. 3281938.
More generally, a [n, m] linear error-correcting code over Galois field GF(q) is a m-dimensional linear subspace of GF(q)n. GF(q) is a finite field with q elements. GF(q)n is a set of vectors (numerical vectors) obtained when n elements of GF(q) are arranged. The numerical vectors over GF(q) will be written as row vectors according to custom.
In the conventional encoding that utilizes a linear code, data is encoded as follows. First, define a basis of [n, m] linear error-correcting codes (hereinafter referred to as the linear code(s) C) as (g1, . . . , gm). A string of length m to be encoded is expressed by the following formula (13) as a numerical vector over GF(q). Note that there are various examples of the linear codes C, such as Hamming codes, BCH codes, and Goppa codes, which are described in standard textbooks for coding theory. (For example, “The Theory of Error-Correcting Codes,” F. J. MacWilliams and N. J. A. Sloane, NORTH-HOLLAND, ISBN: 0-444-85193-3/0-444-85009-0/0-444-85010-4.)x=(x1, . . . , xm)   (13)
In the following, such data will be referred to as a vector (of length m) or a vector of length m over GF(q). This is encoded into a vector f(x) belonging to the linear code C by the following formula (14). Of course, arithmetic is carried out in GF(q). For example, when q is a prime number, it is carried out with q numbers “0, 1, . . . , q−1” and the mod-q arithmetic.
                              f          ⁡                      (            x            )                          =                              ∑                          i              =              1                        m                    ⁢                                    x              i                        ⁢                          g              i                                                          (        14        )            
When gi=(gi1, . . . , gin) (i=1, . . . , m), the following formula (15) is called a generator matrix of the linear code C:
                    G        =                  [                                                                      g                  11                                                            ⋯                                                              g                                      1                    ⁢                    n                                                                                                      ⋮                                                                                                                          ⋮                                                                                      g                                      m                    ⁢                                                                                  ⁢                    1                                                                              ⋯                                                              g                  mn                                                              ]                                    (        15        )            
Such a publicly known encoding is an [n, m] encoding as stated above, and specially in order to specifically designate an encoding, the above-mentioned encoding is referred to as [n, m] encoding designated by the generator matrix G. In this [n, m] encoding, the information of m digits are sent out using n digits (elements of GF(q)). A linear code C (that is, [n, m] encoding designated by a generator matrix G) is used most often in the case of q=2. In this case, GF(q)={0, 1}. Note that in the case of q=2, “digits” are called a “bit.” Also note that detailed examples of linear codes C and their generator matrices G are also variously described in the above-mentioned standard textbook for coding theory.